package 力扣日常刷题.木22一月.第05天0113;

import java.util.*;

/**
 * @author 帅小伙
 * @date 2022/1/13
 * @description
 */
public class Demo08回溯中等组合总和 {


    ArrayList<List<Integer>> ans = new ArrayList<>();
    Deque<Integer> path = new LinkedList<>();
    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        dfs(candidates,target,0);
        return ans;
    }

    void dfs(int[] candidates, int target,int index){
        if(target == 0){
            ans.add(new LinkedList<>(path));
            return ;
        }
        if(index == candidates.length || target < 0) return;
        path.addLast(candidates[index]);
        dfs(candidates,target - candidates[index],index+1);
        path.removeLast();
        while(index < candidates.length-1 && candidates[index] == candidates[index + 1]){
            index++;
        }
        dfs(candidates,target,index+1);

    }

}
